package com.zjsru.oneDay;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 有效可见点的最大数
 *
 *
 * 输入：points = [[2,1],[2,2],[3,3]], angle = 90, location = [1,1]
 * 输出：3(可见的点数)
 * 解释：阴影区域代表你的视野。在你的视野中，所有的点都清晰可见，尽管 [2,2] 和 [3,3]在同一条直线上，你仍然可以看到 [3,3] 。
 *
\
 */
public class visiblePoint {
    public int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {
        int sameCnt = 0;
        int locationX = location.get(0);
        int locationY = location.get(1);
        // 获得每一个点和location位置的点的角度
        List<Double> polarDegrees = new ArrayList<>();
        for (int i = 0; i < points.size(); i++) {
            int x = points.get(i).get(0);
            int y = points.get(i).get(1);
            if (x == locationX && y == locationY) {
                sameCnt++;
                continue;
            }
            Double degree = Math.atan2(x - locationX, y - locationY);
            polarDegrees.add(degree);
        }
        // 排序
        Collections.sort(polarDegrees);

        int m = polarDegrees.size();
        for (int i = 0; i < m; i++) {
            polarDegrees.add(polarDegrees.get(i) + 2 * Math.PI);
        }
        int maxCnt = 0;
        Double toDegree = angle * Math.PI / 180;
        for (int i = 0; i < m; i++) {
            int iteration = binarySearch(polarDegrees, polarDegrees.get(i) + toDegree, false);
            maxCnt = Math.max(maxCnt, iteration - i);
        }
        return maxCnt + sameCnt;
    }

    public int binarySearch(List<Double> nums, Double target, boolean lower) {
        int left = 0; int right = nums.size() -1;
        int ans = nums.size();
        while(left <= right){
            int mid = (left + right)/2;
            if(nums.get(mid) > target || ( lower && nums.get(mid)>= target)){
                right = mid -1;
                ans = mid;
            }else{
                left = mid + 1;
            }
        }
        return ans;
    }

    public static void main(String[] args){
        //Integer[][] in1 = new Integer[][]{{2,1},{2,2},{3,3}};
        List<List<Integer>> points = new ArrayList<List<Integer>>();//points = [[2,1],[2,2],[3,3]]
        int angle = 90;
        Integer[] in2 = new Integer[]{1,1};
        List<Integer> location = new ArrayList<>(Arrays.asList(in2));//location = [1,1]
        visiblePoint visiblePoint =new visiblePoint();
        int result = visiblePoint.visiblePoints(points,angle,location);
        System.out.println(result);
    }
}
